COMMENT ⊗   VALID 00011 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	I. Not applicable.
C00003 00003	II. Biographical information.
C00004 00004	III. Bibliographic information
C00005 00005	2. Statement by John McCarthy about important Genesereth publications.
C00018 00006	3. Statement by John McCarthy about the MRS language.
C00022 00007	IV. The Candidates Role
C00025 00008	V. Evaluation of teaching.
C00026 00009	VI.
C00027 00010	Report on Michael Genesereth's scholarship by John McCarthy
C00029 00011	VII.
C00031 ENDMK
C⊗;
I. Not applicable.
II. Biographical information.
	Biography is attached.
III. Bibliographic information
1. Bibligraphy is attached.

2. Statement by John McCarthy about important Genesereth publications.

DART, see message about why it's different msg.msg[1,jmc]/418p
An overview of meta-level architecture (82)
Conjunct ordering and controlling recursive inference

Papers on control of reasoning

	An intellectual problem to be solved by a computer can be
regarded has having two parts.  The first is to find the relevant
facts that determine the solution, and the second is to
reason with these facts and get the solution.  One of the discoveries
of the early 1970s and built into the programming language Prolog
is that it is often possible to standardize the reasoning method
and work directly from the expression of the facts in the language
of predicate calculus.  Given the goal of finding some objects (e.g.
x, y and z), satisfying certain ccnditions, a Prolog program will
work from the goal and the facts in the database in a standard
systematic way.  Prolog embodies one way of doing this and the simple
way of using Genesereth's MRS system does it in another.

	However, on more difficult problems the simple standard ways
of using the facts don't work.  The search becomes enormous.  Therefore,
it is necessary to reason about the structure of the
facts and the goal and decide on a strategy for using the facts.  We
can think about this at two levels.  On the first level, the programmer
decides on the strategy for using the facts, and it is important that
the programming language permit him to express this strategy in a
straightforward way.  Genesereth's MRS (for Meta-level Reasoning System)
permits more complex strategies to be expressed straightforwardly than
does Prolog.  On the second and higher level, the program itself must
reason about the structure of facts and goals.

	Most of Genesereth's research concerns the problems of controlling
reasoning, i.e. the strategies for using facts to achieve goals.  The
MRS system is intended both to permit the programmer to express his
strategy if he knows it and to permit him to make the computer itself
search for the best strategy again using controlled logical reasoning ---
this time from ``metafacts'' relevant to determining good strategies.

	Genesereth's ideas on how to do this have been developing.  An
ambitious approach to controlling programs at the meta-level
is contained in the first paper.

``An Overview of Meta-Level Architecture'' by Michael R. Genesereth and
David E. Smith.  This is a revision of an earlier paper by Gensereth
only.

	The main content of this paper is a collection of ways of partially
specifying computer programs by logical assertions.  These assertions make
explicit information about the program that is ordinarily implicit in the
syntactic structure of the program.  Making the information explicit and
piecemeal allows the metareasoning program to observe features of the
object program, to relate them to other facts and to the properties of
changed programs.  Concerned that too much explicit meta-level reasoning
about the program while it is running may make it very slow led Genesereth
and his student Smith to discuss ``compiling'' the meta-level reasoning
into the object program itself.  The future work on MRS seems to have
moved in somewhat different directions than those proposed in this paper,
but, in my opinion, the ideas of the paper and especially the way of giving
partial information about the program in logic are very important and
will be influential in the long run.


"Ordering Conjunctive Queries" by David E. Smith and Michael Genesereth

	While proposals that meta-level reasoning are quite old (Genesereth
refers to my 1959 paper), actually doing it has often foundered on details.
Therefore, it is important to isolate cases in which one can give practical
ways of doing the meta-reasoning.  The present paper is one of these.

	A common problem is to find a collection (say x, y and z) of objects
satisfying a condition that is the conjunction of simpler conditions.
An example contained in the
paper is to find a file in the Scribe language larger than 100 pages
belonging to a member of a given user's directory group.  The usual
way of doing this is to find objects (e.g. x, y and z) that satisfy
the first condition and then check to see if they satisfy the remaining
conditions.  If all the conditions are satisfied, the program wins, but
typically some condition will fail and it is necessary to {\it backtrack}
to an earlier condition and find another collection of objects that
satisfies the earlier condition and again check the later conditions.
This backtracking search for objects satisfying a conjunction of conditions
is the basis of the Prolog language and Genesereth's MRS does it too.
The amount of work done in solving the problem depends on the order
in which the conditions are examined.  In Prolog and other languages,
including MRS, the order is chosen by the programmer in advance.  However,
in certain problems, there isn't an optimal order that can be chosen
independent of the data, and the program will have to choose an order
of the conjuncts before it starts the search.

	The present paper discusses the criteria for ordering the
conjuncts in order to minimize work.  It is the most thorough analysis
of this problem in the published literature, and it constitutes an
important step towards making computer programs do this ordering
themselves, i.e. to plan the structure of their searches.

``Controlling Recursive Inference'' by David E. Smith, Michael R. Genesereth
and Matthew L. Ginsberg.

	This paper covers another important case of control of reasoning.
An important form of reasoning is one in which goals give rise to
subgoals and these to subsubgoals etc.  The problem addressed by the
paper is the etc.  Namely, it is necessary to avoid the infinite
generation of subgoals, and this can often be done by recognizing
that certain proposed subgoals cannot contribute to the solution
of the problem.  A variety of ways of doing this are proposed in the
paper and some relevant theorems are proved.  The theorems take
the form of assertions that under certain conditions, certain
subgoals cannot contribute to the solution of the problem and
hence can be ``pruned''.

``Use of Design Descriptions in Automated Diagnosis'' by Michael R. Genesereth

	Automated diagnosis problems have been a staple of artificial
intelligence, especially the expert systems approach.  Most of the
expert systems, e.g. the famous MYCIN of 1974, embody collections of
rules going from symptoms to diagnosis.  For example, MYCIN has rules
like ``If the patient has fever and swollen cheeks and the laboratory
tests give a certain shape bacteria from a certain part of the body,
then the patient has mumps with certainty-factor 0.7''.  Genesereth
explores a different approach to diagnosis.  This involves having a
description of the normal structure and functioning of the object being
diagnosed.  When a malfunction is observed an attempt is made to ascribe
it to a defect in one of the components of the system or one of
their interconnections.  The parts of the system and their interconnections
are described in first order logic, and the possible defects that
a part or connection may have are similarly described.  An MRS program
can then to the diagnosis.

	Raymond Reiter of the University of Toronto says, ``Genesereth's
major cotnribution in this area was to show how various previous ad hoc
computational and representational schemes for diagnosis from first
principles have uniform logical and theorem proving foundations.  Thii
insight not only provided a significant generalization, but it also led
to DART, a working system, based on a resolution style theorem prover.
I should also add that this paper, and DART as well, provided the first
means for automatic test generation of which I am aware.  All things
considered, I think this is a very important paperwhich will have a
major impact on the future theory and design of diagnostic systems''.
3. Statement by John McCarthy about the MRS language.

	We include here a section on Genesereth's MRS system for writing
expert systems, because such things, like works of art or designs for a
computer that are actually built, can have an importance beyond the
publications that their designers may write about them.  This is especially
important in this case, because a full description of MRS is not
included among Genesereth's papers, although there is a quite good
users' manual for the system written by one of Genesereth's students,
Stuart Russell.  While there should be a major paper about MRS, it
is quite common in computer system building to make to with a manual,
and also for the system designer to delegate the task of writing it.

	MRS is a system for writing expert systems.
There are several such systems including the commercial systems
KEE, ART and Knowledgecraft and university-produced systems such
as OPS-5.  Indeed the subject goes back to the 1960s GPS (general
problem solver) of Newell and Simon.


	The MRS language is distinguished from the other expert systems
partly by its use of metalogical statements and its use of logical
reasoning in reasoning about its domain level statements.  Many
systems do logical reasoning at the domain level,
but the meta-level control provided, when there is any at all, is by
special kinds of statements rather than by logical reasoning.
This is true, for example, of the logic programming language Prolog,
and one of the important motives for MRS is the need to go beyond
Prolog in this respect.

	The idea that meta-level reasoning should be done is quite old,
but its advocates have not previously been able to put it into actual
running systems.  MRS is the first system to actually do meta-level
logical reasoning.  The letter by Reiter discusses the place of MRS in
thinking about meta-level control.

	As such it has excited widespread interest.  Approximately
120 university and industrial organization have paid $200 (universities)
or $500 to have copies made.
IV. The Candidates Role

	A. As a tenured associate professor, Genesereth is expected to
continue the role he has filled as an assistant professor.  This has
included (a) his personal research (b) the supervision of graduate
students in his area of artificial intelligence (c) taking charge
of the main introductory artificial intelligence course.  (c) is
worthy of special comment.  Before Genesereth took charge of this
course, it was most often taught as a survey of important papers
in the field.  Genesereth was the first to organize it as systematic
scientific course, treating the various problems and paradigms
of artificial intelligence via controlled logical reasoning.  His
ability to organize the course and teach it to very large numbers
of students has been important to the Department and will continue
to be important.  He is the best we have in artificial intelligence
at this work.

	B. We expect him to be successful, because he has been successful.

	C. His role has been and will be essentially within  the
Computer Science Department.

	D. Genesereth has filled an important role in developing the
master's program in artificial intelligence.  He was on the curriculum
committee that defined the computer science undergraduate program, and
we expect him to play an important role in the further development of
that program.

He has served on the following CSD Committees:

Curriculum 
Comprehensive Examination
PhD Admissions 
MS in Computer Science
MS in Artificial Intelligence
Facilities 

He has also served on the interdepartmental committees

Mathematical and Computational Sciences 
Medical Information Sciences
V. Evaluation of teaching.

pass the buck to Nils
VI.

B. (Only B is applicable).

1. An ad hoc committee was appointed by the Chairman of the Department.
The committee made a list of university and other researchers
in artificial intelligence at comparable stages in their careers.
It also made a list of prominent people in the field from whom
to solicit letters.  These latter are about the same as we
have used on previous occasions.  Our letter and all replies are
attached.

[praise of referees; Nils will do it].

2. The evaluation committee included Professors McCarthy (chairman),
Feigenbaum, Ullman and Nilsson.

Report on Michael Genesereth's scholarship by John McCarthy

	The problem on which Michael Genesereth has worked since
he came to Stanford is key to artificial intelligence.  This is
the control of logical reasoning by statements in a metalanguage.
Genesereth has developed a programming language called MRS (for
Meta Reasoning System) with the aid of his students that is the
only such system in practical use, even though the need for
such a system has been known since the middle 1970s.

	A non-technical (I hope) description of the problem
of control of reasoning was included in the introduction to the
section that describes Genesereth's publications.

	Apart from the discussion of the papers and that of the MRS system
there are a few remarks worth making.  The first, as attested by many of
the letters, is that Genesereth has an excellent scholarly knowledge of
previous work in the fields that interest him.  This prevents him
from re-inventing previous methods and results.  The second is that
he has very broad interests and generates many ideas, some of which
he hasn't found time to pursue.  In my opinion, the ideas expressed
in his ``Overview of meta-level architecture'' present especially
many possibilities.
VII.

A. The most significant reservation was expressed by Prof. Allen Newell
of Carnegie-Mellon University.  He considered Douglas Lenat more brilliant,
though less steady and able to lead students.  The Computer Science
Department had previously recommended Lenat for tenure though not
unanimously, and the recommendation was turned down by Humanities
and Science.  Newell also considered that Genesereth unlikely to
revolutionize computer science.  Newell has quite high standards
as to what would constitute a revolution, and also he has a different
philosophy of artificial intelligence than the one Genesereth shares
with some other members of the Stanford department.  In spite of
his reservations, Newell recommended that Genesereth be promoted
to tenure.

Newell and one or two others also considered Hector Levesque of the
University of Toronto to be better.  We don't agree with this
opinion, because we regard Levesque's work as somewhat specialized
and not as fundamental to artificial intelligence as Genesereth's
work on the control of logical reasoning.

B. The tenured members of the Computer Science Department.

C. Yes.

D. Yes.